/**
 * @file 哈希、双指针
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-10
 * 
 * @copyright Copyright (c) 2021
 * 
 * 1.两数之和
 * 15.三数之和
 * 18.四数之和
 * 454.四数相加II -- 哈希
 * 1099.小于k的两数之和 -- 会员题醉了
 * 259.较小的三数之和 -- 会员题醉了
 * 16.最接近的三数之和
 * 611.有效三角形个数 -- 枚举第三边
 */

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    // 1. a + b = target
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = mp.find(target - nums[i]);
            if (it != mp.end()) {
                return {i, it->second};
            }
            mp[nums[i]] = i;
        }
        return {-1, -1};
    }
    // 15. a + b + c = 0
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        // 去重
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        // print(nums); // -4 -1 -1 0 1 2
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int a = nums[i];
            if (i != 0 && a == nums[i - 1]) {
                continue;
            }
            int j = i + 1, k = n - 1;
            while (j < k) {
                int b = nums[j], c = nums[k];
                if (j != i + 1 && b == nums[j - 1]) {
                    ++j;
                    continue;
                }
                if (k != n - 1 && c == nums[k + 1]) {
                    --k;
                    continue;
                }
                if (a + b + c == 0) {
                    res.push_back({a, b, c});
                    ++j, --k;
                } else if (a + b + c < 0) {
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return res;
    }
    // 14. a + b + c + d = target
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        // 也是不重复，和三数之和如出一辙
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n; ++j) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int k = j + 1, l = n - 1;
                while (k < l) {
                    if (k != j + 1 && nums[k] == nums[k - 1]) {
                        ++k;
                        continue;
                    }
                    if (l != n - 1 && nums[l] == nums[l + 1]) {
                        --l;
                        continue;
                    }
                    if (nums[i] + nums[j] == target - nums[k] - nums[l]) {
                        res.push_back({nums[i], nums[j], nums[k], nums[l]});
                        ++k, --l;
                    } else if (nums[i] + nums[j] < target - nums[k] - nums[l]) {
                        ++k;
                    } else {
                        --l;
                    }
                }
            }
        }
        return res;
    }
    // 454. 四数相加II
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        // 分组打表求和，表内 存A+B {a+b, 次数}
        // C+D 查表-a-b，查到就加到cnt上
        int cnt = 0;
        int n = nums1.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ++mp[nums1[i] + nums2[j]];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                auto it = mp.find(-nums3[i] - nums4[j]);
                if (it != mp.end()) {
                    cnt += it->second;
                }
            }
        }
        return cnt;
    }
    // 16.
    int threeSumClosest(vector<int> &nums, int target)
    {
        // 要找最接近的数，不能打表
        // 排序 + 双指针
        int n = nums.size();
        std::sort(nums.begin(), nums.end());
        int diff = 10000;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (abs(sum - target) < diff) {
                    diff = abs(sum - target);
                    res = sum;
                }
                if (sum == target) {
                    return target; // 唯一解
                } else if (sum < target) {
                    ++j;
                } else {
                    --k;
                }
            }
        }
        return res;
    }
    // 611.
    int triangleNumber(vector<int> &nums)
    {
        // sort a < b < c
        // a + b > c
        // 枚举最长边，从后往前
        int cnt = 0;
        int n = nums.size();
        std::sort(nums.begin(), nums.end());
        for (int k = n - 1; k >= 0; --k) {
            int i = 0, j = k - 1;
            while (i < j) {
                if (nums[i] + nums[j] > nums[k]) {
                    cnt += max(j - i, 0);
                    --j;
                } else {
                    ++i;
                }
            }
        }
        return cnt;
    }
};

Solution solve = Solution();

void test15()
{
    vector<int> nums = {-1, 0, 1, 2, -1, -4};
    // vector<int> nums = {-2, 0, 0, 2, 2};
    vector<vector<int>> res = solve.threeSum(nums);
    for (auto &r : res) {
        print(r);
    }
}

void test18()
{
    vector<int> nums = {1000000000, 1000000000, 1000000000, 1000000000};
    vector<vector<int>> res = solve.fourSum(nums, 0);
    for (auto &r : res) {
        print(r);
    }
}

void test454()
{
    vector<int> a = {1, 2};
    vector<int> b = {-2, -1};
    vector<int> c = {-1, 2};
    vector<int> d = {0, 2};
    cout << solve.fourSumCount(a, b, c, d) << endl;
}

void test16()
{
    vector<int> nums = {-1, 2, 1, -4};
    // vector<int> nums = {0, 0, 0};
    int target = 1;
    cout << solve.threeSumClosest(nums, target) << endl;
}
int main()
{
    // test15();
    // test18();
    // test454();
    test16();
    return 0;
}